1. Technical Field
The disclosure relates generally to material flow network analysis, and more particularly, to optimization methods for approximating cycle times within a material flow network.
2. Background Art
A fundamental problem faced in all manufacturing industries is the allocation of material and capacity assets to meet end customer demand. Production cycle times necessitate the advance planning of production starts, interplant shipments, and material substitutions throughout the supply chain so that these decisions are coordinated with the end customers' demand for any of a wide range of finished products (typically on the order of thousands in semiconductor manufacturing). Such advance planning depends upon the availability of finite resources which include: finished goods inventory, work in process (WIP) inventory at various stages of the manufacturing system, and work-center capacity.
Often, there are alternative possibilities for satisfying the demand. Products may be built at alternative locations and within a location there may be choices as to which materials or capacity to use to build the product. The product may be built directly or acquired through material substitution or purchase. When limited resources prevent the satisfaction of all demands, decisions need to be made as to which demand to satisfy and how to satisfy it. This resource allocation problem is often addressed through linear programming.
The allocation of resources also requires consideration of planning through a finite planning horizon. A typical assumption for complex resource allocation models is that the planning horizon is composed of discrete time periods (e.g., hours, days, weeks). For a given time horizon, the smaller the number of periods in the planning horizon (i.e., the greater the aggregation of time), the easier the problem is to solve from a computational perspective. Consequently, planning with fewer time periods will result in shorter execution times. However, from a solution quality perspective, a greater number of time periods, i.e., finer granularity, the greater the accuracy in the resulting solution generated using the model.
Advanced planning and scheduling systems (APSs) are used for determining the flow of production materials at the shop floor level in a manufacturing plant, as well as the flow of materials throughout the supply chain, including interplant material shipments and shipments of finished goods to end consumers. APSs are based on mathematical models for optimizing various metrics including work-in-process (WIP) and inventory levels, capacity utilization, service level considerations based on on-time delivery, and criteria for balancing multi-plant production.
A key to APS models is the modeling of material flows throughout a network formed by an extended supply chain. Such networks can be generalized to a graph G(V,E) for vertices V, representing stocking points (e.g., a part number/plant combination) and the edges E, define the dependencies based on bill-of-material (BOM) or other dependencies. For example, as shown in FIG. 1, if part number (PN) A is produced from component part numbers (PN) B and C, and B and C are produced using their component part numbers (PN) D and E, respectively, and so on, then the graph would have the form illustrated. Another example of a dependency would be the time to ship a material from one inventory stocking point to another (say from a plant to a warehouse, a warehouse to a regional distribution center, or from a regional distribution center to a retail store).
APS models take graphs which define bill-of-material dependencies, such as the example in FIG. 1, and project them into a time domain. Each part number/plant combination has an associated cycle time and together the cycle times for assemblies, components, and subcomponents define a total cycle time for production of a finished product. For instance, FIG. 2 illustrates the total cycle time to produce a finished good part number (PN) A based on cycle times for all components. In the example, the raw material PNs D and E are assumed to have zero cycle time. The total cycle time to produce PN A is the sum of the cycle time for PN A (3 days) and the maximum of the cycle time for component PNs B and C (3 days) resulting in a total cycle time of 6 days. “Cycle times” are sometimes referred to as “lead times” in the field. FIG. 3 illustrates another bill of materials product structure.
For small models a suitable approach is to model cycle times in a predetermined unit of time (e.g., days) and impose a graph structure based on daily time periods, which results in a system of material balance equations that describe the flow of material from raw materials to finished goods. Such equations may have the form:
      I    jma    =            I                        (                      j            -            1                    )                ⁢        ma              +          R      jma        +                  ∑        e            ⁢                        ∑                                    x              ⁢                                                          ⁢                              s                .                t                .                                                                    x                +                                  G                  xmae                                            =              j                                      ⁢                              Y            xmae                    ⁢                      P            xmae                                +                  ∑        n            ⁢              L        jnma              +                  ∑        v            ⁢                        ∑                                    x              ⁢                                                          ⁢                              s                .                t                .                                                                    x                +                                  H                  mav                                            =              j                                      ⁢                  T          xmva                      -                  ∑        n            ⁢                        E          jmna                ⁢                  L          jmna                      -                  ∑        v            ⁢              T        jmav              -                  ∑        k            ⁢                        ∑          q                ⁢                  F          jmakq                      -  where Ijma denotes the inventory at the end of period j for part m at plant a. The terms in the equations denote paths by which material may move to inventory stocking points or be removed from inventory stocking points. For instance, variables Pjmae, Ljnma, Tjmva, and Fjmakq denote production starts, material substitutions, interplant transshipments, and customer shipments of a part, m, in period j, respectively.
Based on the choice of time periods, a set of material balance equations are generated and used to formulate a model for the APS (e.g., a linear, nonlinear or combinatorial optimization model). However, many realistic model sizes impose a need for aggregating across time to reduce the number of material balance equations significantly. Without using aggregation methods, many real world APS models would have a number of decision variables measured in the hundreds of millions and be practically unsolvable due to memory and run time requirements.
Conventional methods of aggregating are based on a myopic rounding procedure that rounds actual cycle times up or down based on their proximity to an aggregate time period. The down-side of this simple aggregation approach is that it can significantly underestimate total cycle times for producing finished products. For instance, consider FIG. 3, in which the total actual cycle time for PN A across all of its components is 9 days. If a set of aggregate time periods is set at 7-day periods (week), then a simple rounding procedure would round the individual cycle time for PN A (3 days) to 0 weeks, and round the individual cycle times for component PN B and PN C to 0 weeks. Thus, the total estimated cycle time for PN A would be inappropriately represented as 0 weeks, which is a poor approximation of the actual total cycle time of 9 days.